Image segmentation, as a technique in the representation of images, is well-known in the fields of computer vision, solid modeling, and image processing and computer graphics. In general, images might have several regions of interests and these image regions can be segmented based on image properties like color, texture, gray level and shape. Once these image regions are segmented, they may be modeled in a structure that can be handled by a suitable region processing algorithm. In general, the model thus used ought to preserve all spatial relationships among image regions and should be compact enough for in-memory representation and accessibility.
Several techniques have been employed for creating such an image representation for region-segmented images. Prominent techniques include a Region Adjacency graph representation method and a Region Adjacency tree representation method. However, the Region Adjacency Graph method for modeling image regions and spatial relationships is oriented towards coding an adjacency (neighborhood) relationship among image regions and fails to capture a containment relationship among them, which increases complexity. When modeled for complex images with a large number of image regions, the graph becomes unwieldy as all adjacency relationships among the image regions are added to it. As the efficiency of the processing algorithms that work on the image model is directly dependent on the accessibility of the image regions, a typical image representation should be compact enough for processing algorithms to efficiently work on. On the other hand, the Region Adjacency Tree, which is a hierarchical representation of image regions, captures a containment relationship among the image regions, but misses the adjacency relationship among them, resulting in loss of granularity.
In general, hierarchical models are attractive as they are simple to implement. Some popular hierarchical models include the Quad tree model, and the Horizontal Vertical (‘HV’) Binary tree model. In the Quad tree model, the image is recursively partitioned into 4 equal regions and these regions form the nodes of the tree. The root node of the Quad tree represents the whole image and the other nodes represent the partitions of the image with the leaf nodes representing the individual small partitions. A HV tree is similar to the Quad tree except in that each node in it can have only two child nodes, and the partition of the nodes alternates between horizontal and vertical bisections of the region. However, representations like the Quad tree and the HV tree are limited in that they cannot represent arbitrary shaped regions in the image, only rectangular partitions of the image.
Another kind of technique for modeling images is based on establishing semantic relationship among image regions, and ignoring the spatial relationship among them. Semantic relationships generally characterize the similarity of image region properties like texture, color or shape. These techniques establish a relationship among image regions based on the similarity of the semantic properties of the image regions, ignoring the spatial relationship among them, which serves to make them generally unsuitable for purposes other than semantic image retrieval. Additionally, image understanding, which is a vital component of semantic image retrieval, cannot be addressed using solely semantics-based image representations. Therefore, hybrid techniques which attempt to characterize both the topology and geometry of the image in a representation model have been developed. These mostly use multiple data structures, however, and lack compactness in their representation. In general, representing images in the form of a graph or tree is commonly preferred as the nodes in them are very easily accessible through the links connecting them.
Most existing techniques are fundamentally limited in that they are purpose designed, i.e. they are built and optimized solely for a specified range of uses, and unsuited or inefficient for applications that are directed otherwise. For example, most hierarchical-only models like the Quad or HV tree have simple and robust image segmentation mechanisms, and, therefore, this general category of representations is used for purposes like segmenting images, but as they lack the ability to model, for example, arbitrarily shaped image regions, they are generally not used for modeling images that possess such characteristics. In general, image representations generated from segmenting images by a specific algorithm are particular to it, and cannot be used for other purposes.
Accordingly, there is a need for a well-designed image representation for generic use. Such a representation may require modeling both image regions and their spatial relationships and representing them in a well-organized, compact structure which has a proven accessibility and robustness.